package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class No131 {
    public static void main(String[] args) {
        String s = "aab";
        partition(s);
    }

    public static List<List<String>> partition(String s) {
        List<List<String>> list = new ArrayList<>();
        backTrack(list,s,new ArrayList<>(),0,0);
        System.out.println(list);
        return list;
    }

    public static void backTrack(List<List<String>> result,String s,List<String> list,int index,int start){
        if(index == s.length()){
            result.add(new ArrayList<>(list));
            return;
        }
        if(index<s.length()-1){
            backTrack(result,s,list,index+1,start);
        }
        String substring = s.substring(start,index+1);
        if(isHui(substring)){
            list.add(substring);
            backTrack(result,s,list,index+1,index+1);
            list.remove(list.size()-1);
        }
    }

    public static boolean isHui(String s){
        int i=0,j=s.length()-1;
        while(i<j){
            if(s.charAt(i)!=s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}
